class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }
    int getRandom(vector<int>& nums,int l,int r)
    {
        int a=rand();
        return nums[a%(r-l+1)+l];
    }
    void qsort(vector<int>& nums,int l,int r)
    {
        if(l>=r)return;
        int key=getRandom(nums,l,r);
        int i=l,left=l-1,right=r+1;
        while(i<right)
        {
            if(nums[i]<key)swap(nums[++left],nums[i++]);
            else if(nums[i]==key)i++;
            else swap(nums[--right],nums[i]);
        }
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
};
